Programmable logic devices (“PLDs”) are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the field programmable gate array (“FPGA”), typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks (“IOBs”), configurable logic blocks (“CLBs”), dedicated random access memory blocks (“BRAMs”), multipliers, digital signal processing (“DSP”) tiles, processors, clock managers, delay lock loops (“DLLs”), and so forth. Notably, as used herein, “include” and “including” mean including without limitation.
One such FPGA is the Xilinx Virtex® FPGA available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124. FPGAs may be programmed using configuration memory. Other PLDs may be programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These PLDs are known as mask programmable devices. PLDs can also be implemented in other ways, for example, using fuse or antifuse technology. The terms “PLD” and “programmable logic device” include but are not limited to these exemplary devices, as well as encompassing devices that are only partially programmable. For purposes of clarity, FPGAs are described below though other types of PLDs may be used.
Performance of a design instantiated entirely in programmable logic of an FPGA (“FPGA fabric”) for a DSP application was less efficient than instantiation at least part of the design using one or more DSP tiles. Moreover, prior to introduction of a significant architectural change in DSP tiles, DSP tiles when cascaded were subject to use of general routing circuitry of FPGA fabric.
However, in Virtex-4™ FPGAs available from Xilinx, Inc. of San Jose, Calif., a new DSP slice is available. This DSP slice, known as a “DSP48” slice, includes an 18-by-18 (“18×18”) bit two's complement multiplier and a 48-bit sign-extended adder/subtractor/accumulator. In a Virtex-4™ FPGA, a DSP tile includes two DSP48 slices. DSP48 slices within a DPS tile, as well as DSP tiles themselves, may be cascaded without having to use general routing circuitry of FPGA fabric. This facilitates higher performance along with lower power consumption for some DSP-dependent functions.
By using one or more DSP48 slices, there may be a corresponding reduction in use of FPGA fabric for DSP-instantiated applications which may lead to more efficient resource utilization of CLBs and other FPGA resources and which, as indicated above, may be lead to lower power consumption and higher performance. A DSP48 slice provides programmable pipelining of input operands and rounding multiplication away from zero. These and other features are described in additional detail in “XTREME DSP for Virtex-4 FPGAs User Guide,” UG073 (V2.1), Dec. 19, 2005, available on the Internet at http://www.xilinx.com/bvdocs/userguides/ug073.pdf.
Accordingly, it would be desirable and useful to provide for a Fast Fourier Transform (“FFT”) architecture implemented using one or more DSP slices of an FPGA in order to provide for one or more of higher performance, lower power consumption, or enhanced resource utilization for such implementation.